/**
 * 
 */
package calculation.passed2;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author xyyi
 *
 */
public class PlusOne {

	/**
	 * Given a number represented as an array of digits, plus one to the number.
	 */
	public int[] plusOne1(int[] digits) {
	    if(digits.length == 0)
	        return digits;

	    for(int i = digits.length - 1; i >= 0; --i){
	       //Only the digit 9 is interesting
	        if(digits[i] == 9){
	            digits[i] = 0;
	        }
	        else{
	            digits[i]++;
	            break;            //There is no carry to do so we can break.
	        }
	    }
	    //If the most significant digit is 0 prepend a 1
	    if(digits[0] == 0){
	        digits = Arrays.copyOf(digits, digits.length + 1);
	        digits[0] = 1;
	    }
	    return digits;
	}
	public int[] plusOne(int[] digits) {
		ArrayList<Integer> retList = new ArrayList<Integer>(digits.length + 1);
		int carry = 1;
		for (int i = digits.length - 1, sum = 0; i >= 0; i--) {
			sum = digits[i] + carry;
			carry = sum / 10;
			retList.add(sum % 10);
		}

		// need to check carry after loop
		if (carry > 0)
			retList.add(carry);

		int[] result = new int[retList.size()];
		for (int i = 0, size = result.length; i < size; i++) {
			result[i] = retList.get(size - i - 1);
		}
		return result;
	}

	/**
	 * 
	 */
	public PlusOne() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
